package leetcode.editor.cn.q1_300.q50;

/**
 * 递归超时了，想到了动态规划，
 *
 * @author qidi
 * @date 2021-12-27 11:42:29
 */
class Q0091_DecodeWays {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int numDecodings(String s) {
            int len = s.length();
            int[] dp = new int[len + 1];
            dp[0] = 1;
            for (int i = 1; i <= len; i++) {
                if (s.charAt(i - 1) != '0') {
                    dp[i] = dp[i - 1];
                }
                if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0') <= 26) {
                    dp[i] += dp[i - 2];
                }
            }
            return dp[len];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0091_DecodeWays().new Solution();
        System.out.println(solution.numDecodings("27"));
        System.out.println(solution.numDecodings("111111111111111111111111111111111111111111111"));
        System.out.println(solution.numDecodings("123123"));
        System.out.println(solution.numDecodings("12123"));
        System.out.println(solution.numDecodings("10"));
        System.out.println(solution.numDecodings("106"));
        System.out.println(solution.numDecodings("11106"));
        System.out.println(solution.numDecodings("12"));
        System.out.println(solution.numDecodings("226"));
    }
}